package 算法模板;

import java.util.Arrays;

/**
 * @
 * @date 2024/07/01
 */
public class Floyd多源最短路 {

    public static void main(String[] args) {

    }

    /**
     * f[i][j] 就是从 i 到 j 的最短路
     * edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边
     * 有 n 个城市，按从 0 到 n-1 编号
     */
    public int[][] findTheCity(int n, int[][] edges) {
        int[][] w = new int[n][n];
        for (int[] row : w) {
            Arrays.fill(row, Integer.MAX_VALUE / 2); // 防止加法溢出
        }
        for (int[] e : edges) {
            int x = e[0], y = e[1], wt = e[2];
            w[x][y] = w[y][x] = wt;
        }

        int[][] f = w;
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j]);
                }
            }
        }
        return f;
    }


}
